package com.github.wings27.interview.SortAndSearch;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Project Name: common-interview-problems
 * Date Created: 2013/10/18 上午11:43
 *
 * @author wings
 */
public class Sort {

    public static void bubbleSort(int[] array) {
        int m = array.length;
        for (int i = 0; i < m - 1; i++) {
            boolean isSorted = true;
            for (int j = 0; j < m - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    isSorted = false;
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

    public static void selectionSort(int[] array) {
        int m = array.length;
        for (int i = 0; i < m - 1; i++) {
            int minPos = i;
            for (int j = i + 1; j < m; j++) {
                if (array[j] < array[minPos]) {
                    minPos = j;
                }
            }
            int temp = array[i];
            array[i] = array[minPos];
            array[minPos] = temp;
        }
    }

    public static void insertionSort(int[] array) {
        int m = array.length;
        for (int i = 0; i < m - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    public static void optimizedInsertionSort(int[] array) {
        int m = array.length;
        for (int i = 0; i < m - 1; i++) {
            int temp = array[i + 1];
            int j;
            for (j = i + 1; j > 0 && array[j - 1] > temp; j--) {
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
    }

    public static void heapSort(int[] array) {
        int m = array.length;
        PriorityQueue<Integer> arrayHeap = new PriorityQueue<Integer>(m);
        for (int a : array) {
            arrayHeap.add(a);
        }
        for (int i = 0; i < m; i++) {
            array[i] = arrayHeap.poll();
        }
    }

    public static void mergeSort(int[] array) {
        int m = array.length;
        int half = (m + 1) / 2;
        int[] array1 = new int[half];
        int[] array2 = new int[m - half];
        System.arraycopy(array, 0, array1, 0, half);
        System.arraycopy(array, half, array2, 0, m - half);
        if (half > 1) {
            mergeSort(array1);
        }
        if (m - half > 1) {
            mergeSort(array2);
        }
        int pointer1 = 0;
        int pointer2 = 0;
        int pointerNext = 0;
        while (pointer1 < array1.length && pointer2 < array2.length) {
            array[pointerNext++] = (array1[pointer1] < array2[pointer2]) ? array1[pointer1++] : array2[pointer2++];
        }
        System.arraycopy(array1, pointer1, array, pointerNext, array1.length - pointer1);
        System.arraycopy(array2, pointer2, array, pointerNext + array1.length - pointer1, array2.length - pointer2);
    }

    public static void quickSort(int array[]) {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int array[], int left, int right) {
        int pivot;
        if (left < right) {
            pivot = partition(array, left, right);
            quickSort(array, left, pivot - 1);
            quickSort(array, pivot + 1, right);
        }
    }

    public static int partition(int array[], int left, int right) {
        int pivot = array[left];
        while (left < right) {
            while (left < right && array[right] >= pivot)
                right--;
            if (left < right)
                array[left++] = array[right];
            while (left < right && array[left] <= pivot)
                left++;
            if (left < right)
                array[right--] = array[left];
        }
        array[left] = pivot;
        return left;
    }
}
